#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define MAX 10000
#define WINDOWS_NUM 4 //银行的窗口数

// 链表类型：有头的单链表

/****** 事件 ******/
typedef struct{
	long occurTime; //事件发生时刻
	int type;	    //事件的类型
		// type = 0：预计会有下一个用户到达
		// type != 0：为其他值时，表示该用户在type窗口已经正在办理业务（type=1，表示该用户在窗口1正在处理业务）
}LElemType;
typedef LElemType Event; //事件
typedef struct LNode{
	Event data;
	struct LNode *next;
}LNode, *LinkList; 
typedef LinkList EventList; //事件链表类型（有序链表）

/****** 客户 ******/
typedef struct{
	long arrivalTime; //到达时间
	long duration;    //办理业务所需时间
	int id; //用户的id
	int serviceType;//办理的业务类型 
}QElemType;
typedef QElemType Customer; //客户

/****** 客户队列 ******/ 
typedef struct QNode{
	QElemType data;
	struct QNode *next;
}QNode, *QueuePtr;
typedef struct{
	QueuePtr front; //队头
	QueuePtr rear;  //队尾
}LinkQueue;
typedef LinkQueue CustomerQueue; //客户队列

void BankSimulation(int closeTime); //银行模拟
void OpenForDay();			//开店
void CloseForDay();			//关店
int GetMin(LinkQueue q[]);  //得到人最少的窗口
void CustomerArriving(int closeTime); //预计用户到来
void CustomerDeparture(int closeTime); //用户离开

/***** 链表操作 ******/
void InitList(LinkList *pL);
int ListEmpty(LinkList L);
void OrderInsert(LinkList *pL, LElemType en);
void DelFirst(LinkList *pL, LElemType *e);


/***** 队列操作 ******/
void InitQueue(LinkQueue *Q);
int DelQueue(LinkQueue *pQ, QElemType *e);
int EnQueue(LinkQueue *pQ, QElemType e);
int QueueLength(LinkQueue Q);


int totalTime=0, customerNum=0; //累计客户逗留时间，客户数
EventList eventList; //事件表
Event event; //事件
int windowServiceCounts[4] = {0}; // 每个窗口办理的客户数
int windowServiceTypes[4][4] = {0}; // 每个窗口办理的每种业务数 
CustomerQueue windows[WINDOWS_NUM+1]; //窗口，从1开始存储
Customer customer; //客户记录
int main() {
	int closeTime; //关门时间

	srand(time(NULL)); //设置随机种子，注意：一定要在main函数里，不能放在Random()里，否则无效
	
	printf("输入营业的总分钟数：\n>>> ");
	scanf("%d", &closeTime);
	BankSimulation(closeTime);

	return 0;
}

// 银行模拟
void BankSimulation(int closeTime) {
	OpenForDay(); //开门
	while ( !ListEmpty(eventList) ) {
		// 事件队列还有事件没有处理完
		DelFirst(&eventList, &event); //取出第一个事件，并删除
		if (event.type==0) //预计有新用户达到
			CustomerArriving(closeTime); //生成这个用户几点来
		else //用户正在办理业务
			CustomerDeparture(closeTime); //用户离开事件
	}
	CloseForDay();
}

// 银行开门：初始化
void OpenForDay() {
	int i;
	totalTime = 0;  //总时间
	customerNum = 0; //客户数

	InitList(&eventList); //初始化事件列表
	//银行一开门，就预计有下一个用户到来
	event.occurTime=0;
	event.type=0;
	OrderInsert(&eventList, event); //插入到事件列表
	for (i=1; i<=WINDOWS_NUM; i++) {
		InitQueue(&windows[i]); //初始化银行窗口
	}
	printf("\n△ start 预计下一个用户会来（生成下一个用户到达的事件）\n");
}

void CloseForDay() {
	 printf("每个窗口办理业务的人数\n");
        for (int i = 1; i < 5; ++i) {
        	printf("窗口%d:%d",i,windowServiceCounts[i]); 
        }

	printf("\n△ 客户数=%ld，累计客户逗留时间%ld，平均逗留时间%ld\n", customerNum, totalTime, totalTime/customerNum);
}

// 预测用户到达事件
void CustomerArriving(int closeTime) {
	long durtime, intertime;
	int minWindow, serviceType; 
	
	customerNum++; //客户量+1
	printf("\t预测第%d客户", customerNum);

	// 创建用户
	durtime = rand()%15 +1; //一个业务的时间在1-15分钟
	intertime = rand()%6; //用户间隔0-5分钟来一个
	customer.id = customerNum; // 这是今天第几个用户了
	serviceType = rand()%4 +1;//1-4，1表示存款，2表示取款，3表示借贷，4表示还款 
	customer.arrivalTime = event.occurTime + intertime; //到达时间
	customer.duration = durtime;						//客户办事的持续时间
	if ( customer.arrivalTime >= closeTime ) { //用户来的时候已经关门了

		printf("\t× 生成的下一个用户将在第%dmin到达，那时候已经关门了\n", customer.arrivalTime);
			customerNum--;

	} else { //用户来的时候还没有关门
		
		// 插入最短队
		minWindow = GetMin(windows);						//得到人数最少的队列
		EnQueue(&windows[minWindow], customer);				//插入最短的队伍
		windowServiceCounts[minWindow]++;
        switch(serviceType){
        	case 1:{
        		printf("将在第%dmin到达,办理的业务为取款,办理业务需要%dmin，到窗口%d排队",customer.arrivalTime,customer.duration,minWindow);
				break;
			}
			case 2:{
				printf("将在第%dmin到达,办理的业务为还款,办理的业务需要%dmin,到窗口%d排队",customer.arrivalTime,customer.duration,minWindow);
				break;
			}
			case 3:{
				printf("将在第%dmin到达,办理的业务为借贷，办理的业务需要%dmin,到窗口%d排队",customer.arrivalTime,customer.duration,minWindow);
				break;
			}
			case 4:{
				printf("将在第%dmin到达，办理的业务为还款,办理的业务需要%dmin,到窗口%d排队",customer.arrivalTime,customer.duration,minWindow);
				break;
			}
			default:{
				printf("抱歉，我们银行没有此业务，请去其他银行咨询。");
				break;
			}
		}
	//	printf("将在第%dmin到达，办理业务需要%dmin，到窗口%d排队", customer.arrivalTime, customer.duration, minWindow);
		
		// 插入离开事件
		event.occurTime = customer.arrivalTime + durtime; //预计离开时间
		printf("，预计离开时间%dmin\n", event.occurTime);
		event.type = minWindow; //窗口
		if ( QueueLength(windows[minWindow]) ==1 ) //当前队伍只有他一个人
			OrderInsert(&eventList, event); //插入离开事件，让这个人离开
		
		// 预计下一个用户的到达
		event.occurTime = customer.arrivalTime; //创建下一个用户到达的事件
		event.type = 0;
		if ( event.occurTime < closeTime ) //如果预计时间已经关门了，就退出
			OrderInsert(&eventList, event);

	}
}

// 事件处理完成，用户离开
void CustomerDeparture(int closeTime) {
	int type; //窗口号
	QNode *p;
	QElemType qe;

	type = event.type; //窗口号
	DelQueue(&windows[type], &customer); //得到出队的用户
	printf("窗口%d %d号用户离开 ", type, customer.id);
	if (event.occurTime > closeTime) { //用户办理业务时已经关门了
		printf("× 他是%dmin到达的，预计办理业务所花费的时间为%dmin，预计离开时间是%dmin。但排到队时已经是%d了，只好改天再来\n", customer.arrivalTime, customer.duration, customer.arrivalTime+customer.duration ,event.occurTime);
		windowServiceCounts[type]--;
		//printf("用户数量为：%d\n",customerNum);
		customerNum--; //去掉这个用户
		//printf("用户数量为：%d\n",customerNum);
		return ;
	} else {
		printf("√ 离开时间%d（即当前时钟的时间）\n", event.occurTime);
		totalTime += event.occurTime - customer.arrivalTime; //客户等待的时间=当前时间-客户到达店里的时间
		if ( QueueLength(windows[type]) ) {
			// 当前窗口还有人
			
			// 开始处理下一位
			p = windows[type].front->next;
			qe = p->data;
			customer.arrivalTime = qe.arrivalTime; //开始时间
			customer.duration = qe.duration;       //持续时间
			event.occurTime = event.occurTime + customer.duration; //事件的发生时间
			event.type = type;	//type号窗口开始处理该用户
			OrderInsert(&eventList, event); //插入到事件链表中等待离队
		}
	}
}

// 得到人数最少的队列
int GetMin(LinkQueue q[]) {
	int i,k,min;
	int cnt;
	QNode *p;
    min=MAX;
	for (i=1; i<=WINDOWS_NUM; i++) {
		if ( q[i].front == q[i].rear ) { // 该窗口没有人
			cnt = 0; //窗口人数=0
		} else { //该窗口有人
			// 计算目前窗口的人数
			for (cnt=1,p=q[i].front->next; p!=q[i].rear; p=p->next) { 
				cnt++;
			}
		}
		if (min>cnt) {
			min = cnt;
			k = i;
		}
	}
	return k;
}

/***** 链表操作 ******/
// 有头结点的单链表
void InitList(LinkList *pL) { //链表初始化
	*pL = (LNode *)malloc(sizeof(LNode));
	if (!*pL) exit(0);
	(*pL)->next = NULL;
}

int ListEmpty(LinkList L) {
	return L->next==NULL ? 1 : 0; //L的下一个为空 ？ 是空 ： 不空
}

void OrderInsert(LinkList *pL, LElemType en) { //按occurTime从小到大的顺序插入
	LNode *p, *q, *s;

	for (p=*pL,q=p->next; q && q->data.occurTime<en.occurTime; p=q,q=p->next) ; //找到插入位置
	s = (LNode *)malloc(sizeof(LNode)); if (!s) exit(0);
	s->data.type = en.type; s->data.occurTime = en.occurTime;
	p->next = s;
	s->next = q;
}

void DelFirst(LinkList *pL, LElemType *e) {
	LNode *p;
	p = (*pL)->next;
	(*pL)->next = p->next;
	e->occurTime = p->data.occurTime;
	e->type = p->data.type;
	free(p);
}


/***** 队列操作 ******/
// 有头结点的单链表
void InitQueue(LinkQueue *Q) {
	Q ->front = Q->rear = (QNode *)malloc(sizeof(QNode));
	Q ->front->next = NULL;
}

int DelQueue(LinkQueue *pQ, QElemType *e) {
	QNode *p;
	if ( (*pQ).front == (*pQ).rear ) return 0; //空
	p = (*pQ).front->next;
	e->arrivalTime = p->data.arrivalTime;
	e->duration = p->data.duration;
	e->id = p->data.id;
	(*pQ).front->next = p->next;
	if ( (*pQ).rear == p ) //删除一个后，队列变空了
		(*pQ).rear = (*pQ).front;
	free(p);
	return 1;
}

int EnQueue(LinkQueue *pQ, QElemType e) {
	QNode *p;
	p = (QNode *)malloc(sizeof(QNode)); if (!p) exit(0);
	p->data.arrivalTime = e.arrivalTime;
	p->data.duration = e.duration;
	p->data.id = e.id;
	p->next = NULL;
	(*pQ).rear->next = p;
	(*pQ).rear = p;
	return 1;
}

int QueueLength(LinkQueue Q) {
	int cnt=0;
	QNode *p;
	if ( Q.front==Q.rear ) cnt=0;
	else {
		for ( p=Q.front; p!=Q.rear; p=p->next ) cnt++;
	}
	return cnt;
}